package com.lw.leetcode.bingChaJi.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1267. 统计参与通信的服务器
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/4 11:38
 */
public class CountServers {


    public static void main(String[] args) {
        CountServers test = new CountServers();

        // 0
//        int[][] arrs = {{1,0},{0,1}};

        // 0[[0,0,0,0],[1,1,1,1],[0,0,0,1],[0,0,1,1],[0,0,0,1]]
        int[][] arrs = {{0, 0, 0, 0}, {1, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}};

        int i = test.countServers(arrs);
        System.out.println(i);
    }


    public int countServers(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int l = m * n;
        int[] arr = new int[l];
        for (int i = 0; i < l; i++) {
            arr[i] = i;
        }
        int[] items = new int[n];
        Arrays.fill(items, -1);
        for (int i = 0; i < m; i++) {
            int f = -1;
            int a = i * n;
            int[] ints = grid[i];
            for (int j = 0; j < n; j++) {
                if (ints[j] == 0) {
                    continue;
                }
                int t1 = a + j;
                if (f == -1) {
                    f = j;
                } else {
                    arr[t1] = arr[a + f];
                }
                if (items[j] == -1) {
                    items[j] = i;
                } else {
                    int i1 = find(t1, arr);
                    int i2 = find(items[j] * n + j, arr);
                    if (i1 != i2) {
                        arr[i2] = i1;
                    }
                }
            }
        }
        int[] arr2 = new int[l];
        for (int i : arr) {
            arr2[find(i, arr)]++;
        }
        int sum = 0;
        for (int i : arr2) {
            if (i > 1) {
                sum += i;
            }
        }
        return sum;
    }

    private int find(int v, int[] arr) {
        if (v == arr[v]) {
            return v;
        }
        arr[v] = find(arr[v], arr);
        return arr[v];
    }

}
